﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SolverLibrary.Data_Entities
{
    public class SudokuBoard : Board
    {
        ///NOTE: Columns and Rows all begin with 0.

        /// <summary>
        /// Sparse matrix for holding which spaces are occupied and
        /// which are not.
        /// </summary>
        private int[,] sparseMatrix = new int[9,9];

        /// <summary>
        /// Matrix containing the actual values of the items.
        /// </summary>
        private int[,] board = new int[9,9];

        /// <summary>
        /// Dictionary mapping a row to the available numbers in that row.
        /// </summary>
        private Dictionary<int, HashSet<int>> rowToAvailableNumbers = new Dictionary<int, HashSet<int>>();

        /// <summary>
        /// Dictionary mapping a column to the available numbers in that column.
        /// </summary>
        private Dictionary<int, HashSet<int>> columnToAvailableNumbers = new Dictionary<int, HashSet<int>>();

        /// <summary>
        /// Dictionary mapping of a subBoard to the available numbers in that board.
        /// </summary>
        private Dictionary<int, HashSet<int>> subBoardToAvailableNumbers = new Dictionary<int, HashSet<int>>();

        public SudokuBoard()
        {
            this.initialize();
        }

        /// <summary>
        /// Fill in all the available row and column numbers.
        /// </summary>
        private void initialize()
        {
            for (int i = 0; i < 9; ++i)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!rowToAvailableNumbers.ContainsKey(i))
                    {
                        rowToAvailableNumbers.Add(i, new HashSet<int>());
                    }
                    if (!columnToAvailableNumbers.ContainsKey(i))
                    {
                        columnToAvailableNumbers.Add(i, new HashSet<int>());
                    }

                    if (!subBoardToAvailableNumbers.ContainsKey(i + 1))
                    {
                        subBoardToAvailableNumbers.Add(i + 1, new HashSet<int>());
                    }
                    rowToAvailableNumbers[i].Add(j + 1);
                    columnToAvailableNumbers[i].Add(j + 1);
                    subBoardToAvailableNumbers[i + 1].Add(j + 1);
                }
            }
        }

        public Item get(int x, int y)
        {
            if (x < 0 || x > 8)
            {
                throw new ArgumentOutOfRangeException("Invalid x index " + x);
            }
            else if (y < 0 || y > 8)
            {
                throw new ArgumentOutOfRangeException("Invalid y index " + x);
            }
            return SudokuBoardItem.getSudokuBoardItem(board[x,y]);
        }

        public Item get(int i)
        {
            //The indices of our flattened two dimensional array read like you would
            //read a book. The first row's last column is 8 and the second row's first
            //column is 9.
            int column = i;
            int row = 0;
            while (column - 9 >= 0)
            {
                column -= 9;
                ++row;
            }
            return SudokuBoardItem.getSudokuBoardItem(board[column,row]);
        }

        public int[] getOneDimensional()
        {
            int[] flatBoard = new int[81];
            return flatBoard;
        }

        public int[,] getTwoDimensional()
        {
            return this.board;
        }

        public void add(Item item, int x, int y)
        {
            //If the area is already taken, then we have to do additional
            //processing.
            int itemValue = item.intValue();
            if (board[x,y] != 0)
            {
                remove(x, y);
            }
            if (itemValue != 0)
            {
                //Remove the item from the list of available items for
                //the column
                columnToAvailableNumbers[x].Remove(itemValue);
                //Remove the item from the list of available items for
                //the row.
                rowToAvailableNumbers[y].Remove(itemValue);
                //Remove the item from the list of available items
                //for the row.
                int subBoard = determineSubBoard(x, y);
                subBoardToAvailableNumbers[subBoard].Remove(itemValue);
                //Add the item to the sparse matrix as well as the actual 
                //matrix
                sparseMatrix[x,y] = 1;
            }
            board[x,y] = itemValue;
        }

        public int remove(int x, int y)
        {
            int value = board[x,y];
            board[x,y] = 0;
            sparseMatrix[x,y] = 0;
            int subBoard = determineSubBoard(x, y);
            //Add the integer back to being available.
            columnToAvailableNumbers[x].Add(value);
            rowToAvailableNumbers[y].Add(value);
            subBoardToAvailableNumbers[subBoard].Add(value);
            return value;
        }

        public void insertRow(int[] row, int index)
        {
            for (int i = 0; i < 9; i++)
            {
                add(SudokuBoardItem.getSudokuBoardItem(row[i]), i, index);
            }
        }

        public int determineSubBoard(int column, int row)
        {
            if (0 <= row && row <= 2)
            {
                if (0 <= column && column <= 2)
                {
                    return 1;
                }
                else if (3 <= column && column <= 5)
                {
                    return 2;
                }
                else
                {
                    return 3;
                }
            }
            else if (3 <= row && row <= 5)
            {
                if (0 <= column && column <= 2)
                {
                    return 4;
                }
                else if (3 <= column && column <= 5)
                {
                    return 5;
                }
                else
                {
                    return 6;
                }
            }
            else
            {
                if (0 <= column && column <= 2)
                {
                    return 7;
                }
                else if (3 <= column && column <= 5)
                {
                    return 8;
                }
                else
                {
                    return 9;
                }
            }

        }

        private int flatten(int column, int row)
        {
            return column + row * 9;
        }

        public Candidate bestCandidate()
        {
            int smallestIntersection = 9;
            Candidate bestCandidate = new Candidate();
            for (int x = 0; x < 9; x++)
            {
                for (int y = 0; y < 9; y++)
                {
                    if (board[x,y] == 0)
                    {
                        int subBoard = determineSubBoard(x, y);
                        HashSet<int> intersect = new HashSet<int>(
                            intersection(
                                rowToAvailableNumbers[y],
                                columnToAvailableNumbers[x],
                                subBoardToAvailableNumbers[subBoard]
                             ));
                        //Debugging. Remove in production.
//                        Console.WriteLine("Intersection between [{0}], [{1}] and [{2}] is [{3}]",
 //                           String.Join(",",columnToAvailableNumbers[x].ToArray()), 
  //                          String.Join(",",rowToAvailableNumbers[y].ToArray()), 
   //                         String.Join(",",subBoardToAvailableNumbers[subBoard].ToArray()),
    //                        String.Join(",",intersect));
                        if (intersect.Count < smallestIntersection
                            && intersect.Count > 0)
                        {
                            smallestIntersection = intersect.Count;
                            bestCandidate.Row = y;
                            bestCandidate.Column = x;
                            bestCandidate.Candidates = intersect;
                        }
                        if (smallestIntersection == 1)
                        {
                            //Return early. We can't get any better than this.
                            return bestCandidate;
                        }
                    }
                }
            }
            return bestCandidate;
        }

        public override string ToString()
        {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    builder.Append("[").Append(board[j, i]).Append("]");
                }
                builder.Append("\n");
            }
            return builder.ToString();
        }

        /// <summary>
        /// Get the candidate values for the given row and column.
        /// </summary>
        /// <param name="column"></param>
        /// <param name="row"></param>
        /// <returns></returns>
        private int[] candidates(int column, int row)
        {
            return intersection(rowToAvailableNumbers[row], columnToAvailableNumbers[column]);
        }

        /// <summary>
        /// Get the intersection between the two sets.
        /// </summary>
        /// <param name="set1"></param>
        /// <param name="set2"></param>
        /// <returns></returns>
        private int[] intersection(HashSet<int> set1, HashSet<int> set2, params HashSet<int>[] additional)
        {
            IEnumerable<int> initialIntersection = set1.Intersect(set2);
            foreach (HashSet<int> set in additional)
            {
                initialIntersection = initialIntersection.Intersect(set);
            }
            return initialIntersection.ToArray();
        }

        internal bool isFull()
        {
            bool full = false;
            for (int i = 0; i < 9; i++)
            {
                full = rowToAvailableNumbers[i].Count == 0
                       && columnToAvailableNumbers[i].Count == 0
                       && subBoardToAvailableNumbers[i + 1].Count == 0;
                if (!full)
                {
                    break;
                }
            }
            return full;
        }
    }

    public class Candidate
    {
        int row = -1;

        public int Row
        {
            get { return row; }
            set { row = value; }
        }

        int column = -1;

        public int Column
        {
            get { return column; }
            set { column = value; }
        }

        HashSet<int> candidateValues = new HashSet<int>();

        public HashSet<int> Candidates
        {
            get { return candidateValues; }
            set { candidateValues = value; }
        }

        public bool isValid()
        {
            if (row == -1 || column == -1 || candidateValues.Count == 0)
            {
                return false;
            }
            return true;
        }
    }
}
